package algorithem;

import java.util.*;

/**
 * @author Kabutz
 * @date 12-13-2006 (The new/improved Algorithem!)
 */
public class SuDoKu {
	public enum Value {
		ONE, TWO, THREE, FOUR, FIVE, SIX, SEVEN, EIGHT, NINE;

		public String toString() {
			return Integer.toString(ordinal() + 1);
		}

		public static Value convert(int index) {
			return values()[index - 1];
		}
	}

	private static final int GRID = 9;

	private final Map<Position, EnumSet<Value>> numbers = new LinkedHashMap<Position, EnumSet<Value>>();

	public SuDoKu(int... values) {
		if (values.length != GRID * GRID)
			throw new IllegalArgumentException("Bad value count");
		for (int i = 0; i < values.length; i++) {
			Position pos = new Position(i / GRID, i % GRID);
			if (values[i] == 0) {
				numbers.put(pos, EnumSet.range(Value.ONE, Value.NINE));
			} else {
				numbers.put(pos, EnumSet.of(Value.convert(values[i])));
			}
		}
		sieveImpossibleNumbers();
	}

	public void remove(int row, int col, int value) {
		numbers.get(new Position(row, col)).remove(Value.convert(value));
	}

	public boolean solve() {
		do {
			check();
			System.out.println(this);
		} while (sieveImpossibleNumbers() || searchForAnswers()
				|| searchForReallyComplexAnswers() || searchQuadrants());
		for (EnumSet<Value> values : numbers.values()) {
			if (values.size() != 1)
				return false;
		}
		return true;
	}

	private void check() {
		for (Position pos : numbers.keySet()) {
			EnumSet<Value> vals = numbers.get(pos);
			if (vals.size() == 1) {
				checkCorrectness(pos, vals.iterator().next());
			}
			if (vals.size() == 0) {
				throw new IllegalStateException("Position " + pos
						+ " is empty!");
			}
		}
	}

	private boolean searchQuadrants() {
		boolean removed = false;
		Collection<Collection<Position>> quadrants = findQuadrants();
		for (Collection<Position> positions : quadrants) {
			EnumSet<Value> values = EnumSet.noneOf(Value.class);
			EnumMap<Value, Collection<Position>> lookups = new EnumMap<Value, Collection<Position>>(
					Value.class);
			for (Position pos : positions) {
				EnumSet<Value> v = numbers.get(pos);
				if (v.size() > 1) {
					values.addAll(v);
					for (Value value : v) {
						Collection<Position> p = lookups.get(value);
						if (p == null) {
							lookups.put(value, p = new ArrayList<Position>());
						}
						p.add(pos);
					}
				}
			}
			for (Map.Entry<Value, Collection<Position>> entry : lookups
					.entrySet()) {
				Value v = entry.getKey();
				Collection<Position> p = entry.getValue();
				int row = -1;
				int col = -1;
				for (Position position : p) {
					if (row == -1) {
						row = position.getRow();
					} else if (row != position.getRow()) {
						row = -2;
					}
					if (col == -1) {
						col = position.getCol();
					} else if (col != position.getCol()) {
						col = -2;
					}
				}
				if (row >= 0) {
					for (Position pos : numbers.keySet()) {
						if (pos.getRow() == row && !positions.contains(pos)) {
							boolean b = numbers.get(pos).remove(v);
							if (b) {
								System.out
										.println("Removed all " + v
												+ " from row " + row
												+ " where not in quadrant "
												+ positions);
							}
							removed |= b;
						}
					}
				}
				if (col >= 0) {
					for (Position pos : numbers.keySet()) {
						if (pos.getCol() == col && !positions.contains(pos)) {
							boolean b = numbers.get(pos).remove(v);
							if (b) {
								System.out
										.println("Removed all " + v
												+ " from col " + col
												+ " where not in quadrant "
												+ positions);
							}
							removed |= b;
						}
					}
				}
			}
		}
		return removed;
	}

	private Collection<Collection<Position>> findQuadrants() {
		Collection<Collection<Position>> result = new ArrayList<Collection<Position>>();
		for (int i = 0; i < 9; i++) {
			Collection<Position> square = new ArrayList<Position>();
			for (int cell = 0; cell < 9; cell++) {
				square.add(new Position((i / 3) * 3 + cell / 3, (i % 3) * 3
						+ cell % 3));
			}
			result.add(square);
		}
		return result;
	}

	private boolean searchForReallyComplexAnswers() {
		boolean removed = false;
		for (Position pos : numbers.keySet()) {
			EnumSet<Value> vals = numbers.get(pos);
			if (vals.size() > 1) {
				removed |= searchForTuples(vals, pos, pos
						.getHorizontalPositions());
				removed |= searchForTuples(vals, pos, pos
						.getVerticalPositions());
				removed |= searchForTuples(vals, pos, pos
						.getSmallSquarePositions());
			}
		}
		return removed;
	}

	private boolean searchForTuples(EnumSet<Value> vals, Position pos,
			Collection<Position> partnerPositions) {
		boolean removed = false;
		Collection<Position> friends = findTuples(partnerPositions, vals);
		if (friends.size() == vals.size() - 1) {
			for (Position other : partnerPositions) {
				if (!other.equals(pos) && !friends.contains(other)) {
					EnumSet<Value> other_vals = numbers.get(other);
					boolean b = other_vals.removeAll(vals);
					if (b) {
						System.out.println("Removed " + vals
								+ " from position " + other);
					}
					removed |= b;
				}
			}
		}
		return removed;
	}

	private Collection<Position> findTuples(Collection<Position> positions,
			EnumSet<Value> vals) {
		Collection<Position> result = new ArrayList<Position>();
		for (Position pos : positions) {
			if (vals.containsAll(numbers.get(pos))) {
				result.add(pos);
			}
		}
		return result;
	}

	/**
	 * Goes through all the positions and removes numbers that are not possible.
	 * Also checks the correctness of the found numbers.
	 */
	private boolean sieveImpossibleNumbers() {
		boolean removed = false;
		for (Position pos : numbers.keySet()) {
			if (numbers.get(pos).size() != 1) {
				// must be bitwise OR, otherwise it will fall through
				removed |= removeImpossibleNumbers(pos);
			}
		}
		return removed;
	}

	private boolean removeImpossibleNumbers(Position pos) {
		boolean removed = false;
		EnumSet<Value> vals = numbers.get(pos);
		for (Position other : pos.getRelatedPositions()) {
			removed |= vals.remove(getNumber(other));
		}
		return removed;
	}

	private Value getNumber(Position pos) {
		EnumSet<Value> vals = numbers.get(pos);
		if (vals.size() == 1) {
			return vals.iterator().next();
		}
		return null;
	}

	private void checkCorrectness(Position pos, Value val) {
		for (Position other : pos.getRelatedPositions()) {
			if (val == getNumber(other)) {
				throw new IllegalStateException("Error with: " + pos
						+ " clashes with relative " + other);
			}
		}
	}

	private boolean searchForAnswers() {
		for (Position pos : numbers.keySet()) {
			EnumSet<Value> possible = numbers.get(pos);
			if (possible.size() > 1) {
				for (Value value : possible) {
					if (valueNotIn(value, pos.getHorizontalPositions())
							|| valueNotIn(value, pos.getVerticalPositions())
							|| valueNotIn(value, pos.getSmallSquarePositions())) {
						System.out.println(pos + " MUST BE " + value);
						numbers.put(pos, EnumSet.of(value));
						return true;
					}
				}
			}
		}
		return false;
	}

	private boolean valueNotIn(Value value, Collection<Position> positions) {
		for (Position pos : positions) {
			if (numbers.get(pos).contains(value)) {
				return false;
			}
		}
		return true;
	}

	public String toString() {
		StringBuffer result = new StringBuffer();
		for (int row = 0; row < GRID; row++) {
			for (int col = 0; col < GRID; col++) {
				EnumSet<Value> vals = numbers.get(new Position(row, col));
				result.append('[');
				for (Value v : vals) {
					result.append(v);
				}
				result.append(']').append('\t');
			}
			result.append('\n');
		}
		return result.toString();
	}
	
	/**
	 * 
	 * @author Ido
	 * @return
	 */
	public Object[][] getResultGrid() {
		Object[][] data = new Object[9][9];
		for (int row = 0; row < GRID; row++) {
			for (int col = 0; col < GRID; col++) {
				EnumSet<Value> vals = numbers.get(new Position(row, col));
				//result.append('[');
				for (Value v : vals) {
					data[row][col] = v.toString();
				}
					//result.append(v);				result.append(']').append('\t');
			}
//			result.append('\n');
		}
		return data;
		
	}
	
}